# -*- coding: utf-8 -*-

"""给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
输入: l1 = [2, 4, 3], l2 = [5, 6, 4]
输出: [7, 0, 8]
解释: 342 + 465 = 807"""

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
    

def generate_linked_list(arr):
    ls = ListNode()
    p = ls
    for i in arr:
        p.next = ListNode(i)
        p = p.next
    return ls.next


def printf(ls):
    strf = ''
    p = ls
    while True:
        if p is None:
            break
        strf += (', %s' % p.val)
        p = p.next
    print(strf[2:])


class Solution:
    """此题应该是考察单链表的一般操作"""
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        sm = l1.val + l2.val
    
        ls = ListNode(val=sm % 10)
        carry_bit = sm // 10

        p1, p2, p = l1.next, l2.next, ls
        while True:
            if carry_bit == 0:
                if p1 and p2:
                    pass
                if p1 is None and p2 is None:
                    break
                elif p1 is None:
                    p.next = p2.next
                    break
                elif p2 is None:
                    p.next = p1.next
                    break

            if p1:
                num1 = p1.val
                p1 = p1.next
            else:
                num1 = 0

            if p2:
                num2 = p2.val
                p2 = p2.next
            else:
                num2 = 0

            sm = num1 + num2 + carry_bit
            p.next = ListNode(sm % 10)
            carry_bit = sm // 10
            p = p.next
        
        return ls


if __name__ == '__main__':
    # l1 = generate_linked_list([2,4,3])
    # l2 = generate_linked_list([5,6,4])
    
    l1 = generate_linked_list([9,9,9,9,9,9,9])
    l2 = generate_linked_list([9,9,9,9])

    so = Solution()
    
    ls = so.addTwoNumbers(l1, l2)
    printf(ls)
